package org.eoti.math.cf;

import org.eoti.math.MathUtil;

import java.math.BigInteger;
import java.util.concurrent.CopyOnWriteArrayList;

/**
 * The MIT License
 * <p/>
 * Copyright (c) 2009 Malachi de AElfweald (malachid@gmail.com)
 * <p/>
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated
 * documentation files (the "Software"), to deal in the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to the following conditions:
 * <p/>
 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the
 * Software.
 * <p/>
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
 * WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
public class SqrtCF
extends ContinuedFraction
{
	private BigInteger delegate;
	private CopyOnWriteArrayList<BigInteger> pattern;
	private BigInteger repeatingStart = null;
	private BigInteger size = null;
	private BigInteger mod = null;

	public SqrtCF(int num)
	{
		this(BigInteger.valueOf(num));
	}

	public SqrtCF(BigInteger num)
	{
		this.delegate = num;
	}

	public BigInteger getNumerator( BigInteger index ){
		if(pattern == null) computeSequence();
		return (repeatingStart == null) ? null : BigInteger.ONE;
	}

	protected void computeSequence()
	{
		pattern = new CopyOnWriteArrayList<BigInteger>();
		BigInteger m = BigInteger.ZERO;
		BigInteger d = BigInteger.ONE;
		BigInteger a = MathUtil.sqrt( delegate );
		BigInteger a0 = a;
		BigInteger aLast = a.multiply(BigInteger.valueOf(2));
		boolean repeatEnabled = false;
		pattern.add(a);
		if(delegate.equals(a.multiply(a))) return;
		BigInteger mn, dn, an;
		while(true)
		{
			mn = (d.multiply(a)).subtract(m);
			dn = (delegate.subtract( (mn.multiply(mn)) )).divide(d);
			an = (a0.add(mn)).divide(dn);

			if(repeatEnabled)
			{
				for(int i=1; i<pattern.size(); i++)
				{
					if((pattern.get(i)).equals(an))
					{
						repeatingStart = BigInteger.valueOf(i);
						size = BigInteger.valueOf(pattern.size());
						mod = size.subtract(repeatingStart);
						return;
					}
				}
			}
			
			pattern.add(an);

			if(an.equals(aLast))
				repeatEnabled = true;

			a = an;
			d = dn;
			m = mn;
		}
	}

	public BigInteger getDenominator( BigInteger index ){
		if(pattern == null) computeSequence();
		if(repeatingStart == null || ( (index.subtract( repeatingStart )).signum() < 0))
			return pattern.get( index.intValue() );

		index = ((index.subtract(repeatingStart)).mod( mod )).add(repeatingStart);
		return pattern.get( index.intValue() );
	}

	public String toString()
	{
		return String.format("sqrt(%s)", delegate);
	}
}
